30缓存一致性 II
AP SHANTHI博士
本模块的目标是讨论对称共享内存多处理器在真实共享和错误共享未命中方面的性能，并详细阐述基于目录的缓存一致性协议。
在上一个模块中，我们讨论了缓存一致性问题，并指出缓存一致性协议基本上有两种类型。作为回顾，这两种类型如下：
1.基于目录：一块物理内存的共享状态只保存在一个位置，称为目录。还可以分发目录以提高可伸缩性。通信是通过互连网络使用点对点请求建立的。
2. Snoop based：每个缓存有一个物理内存块的数据副本，也有一个该块共享状态的副本，但不保持集中状态。缓存都可以通过某种广播介质（总线或交换机）访问，并且所有缓存控制器监视或窥探介质以确定它们是否具有在总线或交换机访问上请求的块的副本。需要广播，因为缓存信息在处理器中 适用于小型机器（大部分市场）
前面的模块详细讨论了基于窥探的协议。我们将重点关注对称共享内存多处理器的性能，然后详细说明本模块中基于目录的方法。
对称共享内存多处理器的性能：在多处理器系统中，有几个因素会影响性能。我们已经研究了导致单处理器系统未命中的三个 C——容量、冲突和强制。除此之外，在多处理器系统中，我们还有第四个缺失，称为一致性缺失。这些是由于处理器间通信而导致的未命中，以保持一致性。我们现在将详细说明它们。
所述相干性缺失可以分成两个独立的源。第一个来源是通过缓存一致性机制进行数据通信所引起的 真正共享未命中。在基于失效的协议中，处理器对共享缓存块的第一次写入会导致失效以建立该块的所有权。此外，当另一个处理器尝试读取该缓存块中的修改字时，会发生未命中并传输结果块。这两种未命中都被归类为真正的共享未命中，因为它们直接来自处理器之间的数据共享。第二种效应，称为虚假共享，源于使用基于失效的一致性算法，每个缓存块只有一个有效位。当块无效（并且后续引用导致未命中）时，会发生错误共享，因为块中的某个字（不是正在读取的字）被写入。如果写入的字实际上由接收无效的处理器使用，则该引用是真正的共享引用，并且会导致与块大小无关的未命中。但是，如果写入的字和读取的字不同，并且失效不会导致传送新值，而只会导致额外的高速缓存未命中，则这是错误共享未命中。在虚假共享未命中中，块被共享，但缓存中没有真正共享的字，如果块大小是单个字，则不会发生未命中。图 34.1 中的以下示例使共享模式变得清晰。让我们假设 X1 和 X2 都在同一个缓存块中，并且处理器 P1 和 P2 之前已经读取过 X1 和 X2。我们将看到下面显示的操作序列会发生什么，并将它们分类为真正的共享未命中或错误的共享未命中。
在第一种情况下，处理器 P1 修改 X1。此事件是真正的共享未命中，因为 X1 已被 P2 读取并且需要从 P2 中失效。在第二个实例中，P2 读取 X2，它早先被 P1 无效。这个事件是一个错误的共享未命中，因为 X2 被 P1 中的 X1 写入无效，但 X1 的那个值没有在 P2 中使用。在第三种情况下，这个事件又是一个错误的共享未命中，因为包含 X1 的块由于 P2 中的读取而被标记为共享，但 P2 没有读取 X1。包含 X1 的缓存块在被 P2 读取后将处于共享状态，并且需要写未命中才能获得对该块的独占访问。在某些协议中，这将作为升级请求处理，它生成一个总线无效，但不传输缓存块。第四个事件是错误共享未命中，原因与步骤 3 相同。最后一个事件是真实共享未命中，因为正在读取的值是由 P2 写入的。
因此，我们看到一致性缺失在多处理器系统中扮演着重要的角色，并且在处理器之间进行大量数据通信的紧耦合系统的情况下，这种影响更为明显。
分布式共享内存和基于目录的一致性协议：我们已经讨论了 snoopy 协议的缺点。随着处理器数量的增加，内存和通信带宽变得过于苛刻，系统无法扩展到一定程度。这个问题可以通过将内存分配给不同的处理器来解决。这将本地内存流量和远程内存流量分开，大大降低了内存需求。然而，在这种情况下，我们还必须消除一致性协议在总线上为每次缓存未命中广播的需要。
因此，在基于目录的协议中，我们有一个替代 snoopy 协议的方法。顾名思义，它是一个保存所有缓存中所有块状态信息的目录。与分发信息的史努比协议不同，这里的信息仅在目录中可用，每个人都可以访问它以获取任何块的详细信息。
To prevent the directory from becoming the bottleneck, the directory is distributed along with the memory, so that different directory accesses can go to different directories, just as different memory requests go to different memories. A distributed directory retains the characteristic that the sharing status of a block is always in a single known location. This property is what allows the coherence protocol to avoid broadcast. Figure 34.2 shows how a distributed-memory multiprocessor looks with the directories added to each node.
该目录对每个内存块都有一个条目。信息量与内存块数和处理器数的乘积成正比。我们需要跟踪哪些处理器拥有该块的副本以及这些块在每个处理器中的状态。这是在写入期间失效所必需的。最简单的方法是为每个内存块保留一个位向量。当块被共享时，向量的每一位指示相应的处理器是否有该块的副本。当块处于独占状态时，我们还可以使用位向量来跟踪块的所有者。出于效率原因，我们还跟踪各个缓存中每个缓存块的状态。
对于少于 200 个处理器的多处理器来说，这种开销不是问题，因为具有合理块大小的目录开销是可以容忍的。对于更大的多处理器，我们需要一些方法来有效地扩展目录结构。已使用的方法要么尝试为较少的块保留信息（例如，仅在缓存中的块而不是所有内存块中的块），要么尝试通过使用单个位来代表一个小的处理器集合来保留每个条目的较少位。
基于目录的缓存一致性协议：就像侦听协议一样，目录协议必须实现两个主要操作：处理读取未命中和处理对共享的干净缓存块的写入。（处理对当前共享块的写未命中是这两者的简单组合。）要实现这些操作，目录必须跟踪每个缓存块的状态。在一个简单的协议中，这些状态可能如下：
1. 共享——一个或多个处理器缓存了块，并且内存中的值是最新的（以及所有缓存中的值）。
2. Uncached –没有处理器拥有缓存块的副本。
3. 修改 -正好有一个处理器有缓存块的副本，并且它已经写入了该块，因此内存副本已过期。处理器被称为块的所有者。
尽管状态和转换与史努比协议的状态和转换相同，但为交易采取的动作是不同的。与在 snoopy 协议中完成的广播不同，这里的通信必须从请求节点发送到目录或从目录发送到其他节点。因此，我们根据其角色定义不同类型的节点。他们是：
的本地节点是节点，其中的请求起源
该主节点是节点，在存储位置和地址驻留的目录项。物理地址空间是静态分布的，因此包含给定物理地址的内存和目录的节点是已知的。例如，高位可提供节点编号，而低位可提供该 节点上存储器内的偏移量。本地节点也可以是家庭节点。当主节点是本地节点时，必须访问该目录，因为副本可能存在于称为远程节点的第三个节点中。
远程节点是具有缓存块副本的节点，无论是独占的（在这种情况下它是唯一的副本）还是共享的。远程节点可以与本地节点或本地节点相同。在这种情况下，基本协议不会改变，但处理器间消息可能会替换为处理器内消息。
图 34.3 显示了在处理器和目录之间发送的用于处理未命中和保持一致性的消息。基本操作与snoopy协议相同。下面给出了消息的解释。
1. 第一个是读取未命中，它从本地缓存发送到主目录。消息的格式是处理器名称 P 和地址 A。目录获取读取未命中，请求数据并将处理器 P 包含在共享节点列表中。
2. 对于写未命中，请求从本地缓存转到主目录。数据再次发送，处理器成为块的唯一所有者。
3. 当本地缓存要进行写操作时，从本地缓存向主目录发送无效消息。
4. 主目录依次向所有缓存了该地址的远程缓存发送无效信息。
5. 当来自本地节点的数据请求时，主目录从远程缓存中获取数据并将其发送到本地缓存。它还包括共享者列表中的本地缓存。
6. 这是为了响应写请求而发生的。主目录从远程缓存中获取数据，并且远程缓存的副本也无效。
7. Data value reply is the sending of the data from the home directory to the local cache requesting it.
8. Data write back is the remote cache writing back the data to the home directory. Data value write backs occur for two reasons: when a block is replaced in a cache and must be written back to its home memory, and also in reply to fetch or fetch/invalidate messages from the home. Writing back the data value whenever the block becomes shared simplifies the number of states in the protocol, since any dirty block must be exclusive and any shared block is always available in the home memory.
示例目录协议：要完成的操作相同，操作顺序也相同。唯一的区别是，不是在总线上广播请求，而是将请求转到主目录，然后主目录执行适当的操作。内存块可以在未缓存状态下可用，即，不在任何缓存中缓存，共享状态，在一个或多个缓存中读取，或独占状态，在其中它被修改并且仅在一个块中可用。详情如下。
• 对于未缓存的块：
– 阅读小姐
• 请求节点向主目录提出请求，该目录发送请求的数据并成为唯一的共享节点，现在块被共享。
– 写小姐
• 请求节点向主目录提出请求，请求节点被发送请求的数据并成为共享节点，块现在是独占的。
• 对于共享块：
– 阅读小姐
• 请求节点向主目录提出请求，请求节点从内存中发送请求的数据，并将该节点添加到共享集中。
– 写小姐
• 请求节点向主目录提出请求，请求节点被发送值，共享集中的所有节点都 发送无效消息，共享集中只包含请求节点，块现在是独占的。
• 对于独占块：
– 阅读小姐
• 请求节点向主目录发送请求，向所有者发送数据获取消息，块变为共享，所有者将数据发送到目录，数据写回内存，共享者集包含旧所有者和请求者。
– 数据回写
• 块变为未缓存，共享者集为空。
– 写小姐
• 消息被发送给旧所有者以使其无效并将值发送到目录，请求者成为新所有者，块保持独占。
图 34.4 显示了基于目录的协议中各个缓存块的状态转换图。图 34.5 显示了目录的状态转换图。状态和转换与前面讨论的相同。
就像在史努比协议的情况下一样，这里我们也需要处理非原子内存事务。有限的缓冲区大小也会导致问题，必须加以处理。实际多处理器中使用的目录协议包含额外的优化。特别是，在该协议中，当一个独占块发生读或写未命中时，该块首先被发送到主节点的目录中。从那里它被存储到本地内存中，并被发送到原始请求节点。商业多处理器中使用的许多协议将数据从所有者节点直接转发到请求节点（以及执行写回主节点）。通过增加死锁的可能性和增加必须处理的消息类型，此类优化通常会增加复杂性。
总而言之，我们研究了对称共享内存处理器的性能。已确定真假共享未命中。我们已经详细研究了分布式共享内存架构中使用的基于目录的缓存一致性协议。
网页链接/支持材料
Computer Architecture – A Quantitative Approach，John L. Hennessy 和 David A.Patterson，第 5 版，Morgan Kaufmann，Elsevier，2011。